(*
 * Materialien zu den zentralen Abiturpruefungen
 * im Fach Informatik ab 2012 in Nordrhein-Westfalen.
 *
 * Klasse TBinarySearchTree
 *
 * NW-Arbeitsgruppe:
 * Materialentwicklung zum Zentralabitur im Fach Informatik
 *
 * Version 2011-01-21
 *)
unit mBinarySearchTree;
interface
uses mBinaryTree, mList;
type
  TItem =class(TObject)
  public
    function isEqual(pItem: TItem): boolean; virtual; abstract;
    function isLess(pItem: TItem): boolean; virtual; abstract;
    function isGreater(pItem: TItem): boolean; virtual; abstract;
  end;

  TBinarySearchTree = class
  private
    binaryTree: TBinaryTree;
  public
    constructor create; virtual;
    function isEmpty: boolean; virtual;
    procedure insert(pItem: TItem); virtual;
    function search(pItem: TItem): TItem; virtual;
    procedure remove(pItem: TItem); virtual;
    function getItem : TItem; virtual;
    function getLeftTree: TBinarySearchTree; virtual;
    function getRightTree: TBinarySearchTree; virtual;
    destructor destroy; override;
  end;

implementation

  constructor TBinarySearchTree.create;
  begin
    binaryTree := TBinaryTree.create;
  end;

  function TBinarySearchTree.isEmpty: boolean;
  begin
    result := binaryTree.isEmpty;
  end;

  procedure TBinarySearchTree.insert(pItem: TItem);
  var
    lItem: TItem;
    lTree,rTree: TBinarySearchTree;
  begin
    if pItem <> nil then
    begin
      if binaryTree.isEmpty then
        binaryTree.setObject(pItem)
      else
      begin
        lItem := TItem(binaryTree.getObject);
        if pItem.isLess(lItem) then
        begin
          lTree:=self.getLeftTree;
          lTree.insert(pItem);
          self.binaryTree.setLeftTree(lTree.binaryTree);
        end  // then
        else
        begin
          if pItem.isGreater(lItem)then
          begin
            rTree := self.getRightTree;
            rTree.insert(pItem);
            self.binaryTree.setRightTree(rTree.binaryTree);
          end; // then
        end; // else
      end; // else
    end; // then
  end;  // insert

  function TBinarySearchTree.search(pItem: TItem): TItem;
  var
    lItem: TItem;
  begin
    if binaryTree.isEmpty or (pItem = nil) then
      result := nil
    else
    begin
      lItem := TItem(binaryTree.getObject);
      if pItem.isLess(lItem) then
        result := self.getLeftTree.search(pItem)
      else
        if pItem.isGreater(lItem) then
          result:=self.getRightTree.search(pItem)
        else
          result:=lItem;
    end;
  end;

  procedure TBinarySearchTree.remove(pItem: TItem);
  var
   lKnoten,glKnoten: TBinaryTree;
   lTree,rTree: TBinarySearchTree;
   lInhalt: TItem;
  begin
    if (not self.isEmpty) and (pItem <> nil)  then
    begin
      lInhalt := self.getItem;
      if lInhalt.isEqual(pItem) then
      begin
        if binaryTree.getRightTree.isEmpty and
           binaryTree.getLeftTree.isEmpty
        then
        begin
          binaryTree.setEmpty;
        end
        else
        begin
          if binaryTree.getRightTree.isEmpty then
          begin
            lKnoten := binaryTree.getLeftTree;
            binaryTree.setObject(lKnoten.getObject);
            binaryTree.setLeftTree(lKnoten.getLeftTree);
            binaryTree.setRightTree(lKnoten.getRightTree);
            lKnoten.destroy;
          end
          else
          begin
            if binaryTree.getleftTree.isEmpty then
            begin
              lKnoten := binaryTree.getRightTree;
              binaryTree.setObject(lKnoten.getObject);
              binaryTree.setLeftTree(lKnoten.getLeftTree);
              binaryTree.setRightTree(lKnoten.getRightTree);
              lKnoten.destroy;
            end
            else
            begin
            glKnoten := binaryTree.getLeftTree;
            while not glKnoten.getRightTree.isEmpty do
            begin
              glKnoten := glKnoten.getRightTree;
            end;
            binaryTree.setObject(glKnoten.getObject);
            self.getLeftTree.remove(TItem(glKnoten.getObject));
            end;
          end;
        end;
      end
      else
      begin
        if lInhalt.isLess(pItem) then
        begin
          rTree := self.getRightTree;
          rTree.remove(pItem);
        end
        else
        begin
          lTree := self.getLeftTree;
          lTree.remove(pItem);
        end;
      end;
    end;
 end;

 function TBinarySearchTree.getItem: TItem;
 begin
   if self.isEmpty then
     result := nil
   else
     result := TItem(binaryTree.getObject);
 end;

 function TBinarySearchTree.getLeftTree: TBinarySearchTree;
 var
   lTree: TBinarySearchTree;
 begin
   if self.isEmpty then
     result := nil
   else
   begin
     lTree := TBinarySearchTree.create;
     lTree.binaryTree := binarytree.getLeftTree;
     result := lTree;
   end;
 end;

 function TBinarySearchTree.getRightTree: TBinarySearchTree;
 var
   lTree: TBinarySearchTree;
 begin
   if self.isEmpty then
     result := nil
   else
   begin
     lTree := TBinarySearchTree.create;
     lTree.binaryTree := binaryTree.getRightTree;
     result := lTree;
   end;
 end;

 destructor TBinarySearchTree.destroy;
 begin
   binaryTree.removeCompletely;
   inherited destroy;
 end;

end.



